package org.apache.commons.graph.algorithms.scc.sample

import com.gitee.wsl.ext.list.pop
import com.gitee.wsl.ext.list.push
import com.gitee.wsl.ext.set.pop
import com.gitee.wsl.ext.set.push
import org.apache.commons.graph.DirectedGraph
import org.apache.commons.graph.algorithms.scc.SccAlgorithm
import org.apache.commons.graph.algorithms.scc.internal.TarjanVertexMetaInfo
import kotlin.math.min

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

/**
 * Implements Tarjan's algorithm is a variation (slightly faster) on KosarajuSharir's algorithm for finding
 * strongly-connected components in a directed graph.
 *
 * @param <V> the Graph vertices type.
 * @param <E> the Graph edges type.
 * @param <G> the directed graph type
</G></E></V> */
internal class TarjanAlgorithm<V, E>(
    private val graph: DirectedGraph<V, E>
) : SccAlgorithm<V> {
    /**
     * Tarjan's algorithm is a variation (slightly faster) on KosarajuSharir's algorithm for finding strongly-connected
     * components in a directed graph.
     *
     * @return the input graph strongly connected component.
     */
    override fun perform(): Set<Set<V>> {
        val verticesMetaInfo: MutableMap<V, TarjanVertexMetaInfo> = HashMap()
        val s = mutableListOf<V>()
        val stronglyConnectedComponents: MutableSet<Set<V>> = LinkedHashSet()
        val index = 0

        for (vertex in graph.vertices) {
            val vertexMetaInfo = getMetaInfo(vertex, verticesMetaInfo)
            val stronglyConnectedComponent: MutableSet<V> = LinkedHashSet()

            if (vertexMetaInfo.hasUndefinedIndex()) {
                strongConnect(graph, vertex, verticesMetaInfo, s, stronglyConnectedComponent, index)
                stronglyConnectedComponents.add(stronglyConnectedComponent)
            }
        }

        return stronglyConnectedComponents
    }

    companion object {
        private fun <V> getMetaInfo(
            vertex: V,
            verticesMetaInfo: MutableMap<V, TarjanVertexMetaInfo>
        ): TarjanVertexMetaInfo {
            var vertexMetaInfo = verticesMetaInfo[vertex]
            if (vertexMetaInfo == null) {
                vertexMetaInfo = TarjanVertexMetaInfo()
                verticesMetaInfo[vertex] = vertexMetaInfo
            }
            return vertexMetaInfo
        }

        private fun <V, E> strongConnect(
            graph: DirectedGraph<V, E>,
            vertex: V,
            verticesMetaInfo: MutableMap<V, TarjanVertexMetaInfo>,
            s: MutableList<V>,
            stronglyConnectedComponent: MutableSet<V>,
            index: Int
        ) {
            var index = index
            val vertexMetaInfo = getMetaInfo(vertex, verticesMetaInfo)
            vertexMetaInfo.index = index
            vertexMetaInfo.lowLink = index
            index++
            s.push(vertex)

            for (adjacent in graph.getOutbound(vertex)) {
                val adjacentMetaInfo = getMetaInfo(adjacent, verticesMetaInfo)
                if (adjacentMetaInfo.hasUndefinedIndex()) {
                    strongConnect(graph, adjacent, verticesMetaInfo, s, stronglyConnectedComponent, index)
                    vertexMetaInfo.lowLink =
                        min(vertexMetaInfo.lowLink.toDouble(), adjacentMetaInfo.lowLink.toDouble()).toInt()
                } else if (s.contains(adjacent)) {
                    vertexMetaInfo.lowLink =
                        min(vertexMetaInfo.lowLink.toDouble(), adjacentMetaInfo.index.toDouble()).toInt()
                }
            }

            if (vertexMetaInfo.lowLink == vertexMetaInfo.index) {
                var v: V
                do {
                    v = s.pop()
                    stronglyConnectedComponent.add(v)
                } while (vertex != v)
            }
        }
    }
}

fun<V, E> SccAlgorithm.Companion.tarjanAlgorithm(graph: DirectedGraph<V, E>):SccAlgorithm<V> = TarjanAlgorithm(graph)